package hero.mps.sort;

import java.util.Arrays;

public class PriorityQueue {
    private int array[];
    private int size;

    public PriorityQueue() {
        array = new int[32];
    }

    /**
     * 上调整堆结构
     *
     * @description 根据最后一个元素的大小，通过上调整操作，保证堆的性质得到维护
     * @return 无返回值
     */
    private void upAdjust() {
        // 子节点索引初始化为最后一个元素的索引
        int childIndex = size - 1;
        // 父节点索引为子节点索引减一后除以2
        int parentIndex = childIndex  / 2;
        // 暂存子节点的值
        int temp = array[childIndex];
        // 当子节点索引大于0且子节点值大于父节点值时循环
        while (childIndex > 0 && temp > array[parentIndex]) {
            // 将父节点的值赋给子节点
            array[childIndex] = array[parentIndex];
            // 子节点索引更新为父节点索引
            childIndex = parentIndex;
            // 更新父节点索引
            parentIndex = parentIndex / 2;
        }
        // 将暂存的子节点值放到最终位置
        array[childIndex] = temp;
    }

    /**
     * 从下往上调整堆结构
     *
     * @description 根据父节点的大小，通过下调整操作，保证堆的性质得到维护
     * @return 无返回值
     */
    private void downAdjust() {
        // 父节点索引初始化为0
        int parentIndex = 0;
        // 子节点索引初始化为1
        int childIndex = 1;
        // 暂存父节点的值
        int temp = array[parentIndex];
        // 当子节点索引小于数组大小时循环
        while (childIndex < size) {
            // 如果子节点索引加1小于数组大小且右子节点的值大于左子节点的值
            if (childIndex + 1 < size && array[childIndex] < array[childIndex + 1]) {
                // 子节点索引加1，指向右子节点
                childIndex++;
            }
            // 如果子节点的值小于等于父节点的值
            if (array[childIndex] <= temp) break;
            // 将子节点的值赋给父节点
            array[parentIndex] = array[childIndex];
            // 更新父节点索引为当前子节点索引
            parentIndex = childIndex;
            // 更新子节点索引
            childIndex = 2 * childIndex + 1;
        }
        // 将暂存的父节点值放到最终位置
        array[parentIndex] = temp;
    }

    /**
     * 向队列中插入一个元素
     *
     * @param key 要插入的元素
     */
    public void enQueue(int key) {
        // 如果队列已满，则进行扩容
        if (size >= array.length) {
            resize();
        }
        // 将元素插入到队列末尾，并更新队列大小
        array[size++] = key;
        // 对队列进行下调整操作，保证堆的性质
        downAdjust();
    }


    /**
     * 从队列中删除一个元素并返回该元素的值
     *
     * @return 返回被删除的元素的值
     * @throws RuntimeException 如果队列为空，则抛出运行时异常
     */
    public int deQueue() {
        // 如果队列的大小小于等于0，则输出队列为空的信息
        if (size <= 0) System.out.println("队列为空！");

        // 将队列首部的元素赋值给head变量
        int head = array[0];

        // 将队列最后一个元素赋值给队列首部的位置，并将队列大小减1
        array[0] = array[--size];

        // 调用upAdjust方法对队列进行上调整操作
        upAdjust();

        // 返回被删除的队列首部的元素值
        return head;
    }


    /**
     * 调整数组大小，将数组容量扩大一倍。
     *
     * @return 无返回值
     */
    private void resize() {
        int newSize = this.size * 2;
        this.array = Arrays.copyOf(this.array, newSize);
    }

    public static void main(String[] args) {
        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.enQueue(3);
        priorityQueue.enQueue(5);
        priorityQueue.enQueue(10);
        priorityQueue.enQueue(2);
        priorityQueue.enQueue(7);
        priorityQueue.enQueue(4);
        System.out.println("出队元素：" + priorityQueue.deQueue());
        System.out.println("出队元素：" + priorityQueue.deQueue());
    }

}
